#include <bits/stdc++.h>
using namespace std;

/*
757. 设置交集大小至少为2
已解答
困难
相关标签
premium lock icon
相关企业
给你一个二维整数数组 intervals ，其中 intervals[i] = [starti, endi] 表示从 starti 到 endi 的所有整数，包括 starti 和 endi 。

包含集合 是一个名为 nums 的数组，并满足 intervals 中的每个区间都 至少 有 两个 整数在 nums 中。

例如，如果 intervals = [[1,3], [3,7], [8,9]] ，那么 [1,2,4,7,8,9] 和 [2,3,4,8,9] 都符合 包含集合 的定义。
返回包含集合可能的最小大小。

 

示例 1：

输入：intervals = [[1,3],[3,7],[8,9]]
输出：5
解释：nums = [2, 3, 4, 8, 9].
可以证明不存在元素数量为 4 的包含集合。
示例 2：

输入：intervals = [[1,3],[1,4],[2,5],[3,5]]
输出：3
解释：nums = [2, 3, 4].
可以证明不存在元素数量为 2 的包含集合。 
示例 3：

输入：intervals = [[1,2],[2,3],[2,4],[4,5]]
输出：5
解释：nums = [1, 2, 3, 4, 5].
可以证明不存在元素数量为 4 的包含集合。 
 

提示：

1 <= intervals.length <= 3000
intervals[i].length == 2
0 <= starti < endi <= 108
*/

// 法一
class Solution {
public:
    int intersectionSizeTwo(vector<vector<int>>& intervals) {
        // greater right AES else left DESC
        sort(intervals.begin(), intervals.end(), [](const auto& a, const auto& b) {
            return a[1] != b[1] ? a[1] < b[1] : a[0] > b[0];
        });

        int ans = 0;
        int last1 = -2, last2 = -1; // max 2 
        for (auto& interval : intervals) {
            int s = interval[0], e = interval[1];
            if (s > last1) {
                // condition 1 当前区间与之前的两个元素无交集，需选e-1和e
                ans += 2;
                last2 = e - 1;
                last1 = e;
            } else if (s > last2) {
                // condition 2 当前区间仅包含last1，需新增e（补充一个元素满足2个交集）
                ans += 1;
                last2 = last1;
                last1 = e;
            }
            // condition 3 当前区间包含last1和last2，无需新增元素
        }
        return ans;
    }
};

// 法二
class Solution {
public:
    int intersectionSizeTwo(vector<vector<int>>& intervals) {
        int n = intervals.size();
        // 排序：右端点升序（优先覆盖后续区间），同右端点左端点降序（优先处理小区间）
        sort(intervals.begin(), intervals.end(), [](const vector<int>& v1, const vector<int>& v2) {
            return v1[1] != v2[1] ? v1[1] < v2[1] : v1[0] > v2[0];
        });
        int p1 = -1, p2 = -1; // 记录包含集合中最近两个元素（最大的两个，最大化覆盖）
        int ans = 0;

        // 普通索引遍历，内存访问更高效
        for (int i = 1; i <= n; ++i) {
            int l = intervals[i-1][0], r = intervals[i-1][1];
            if (l > p2) { // 无交集：需加r-1、r，满足2个交集
                p1 = r - 1;
                p2 = r;
                ans += 2;
            } else if (l > p1) { // 部分交集：仅p2在区间，加r补充到2个
                p1 = p2;
                p2 = r;
                ans += 1;
            }
            // 完全交集（l<=p1）：无需新增元素
        }
        return ans;
    }
};

/**
 * 优化点
 * 循环方式：普通索引 for 比范围 for 更易被编译器优化
 * 排序 lambda：参数类型更明确，减少类型推导开销
 */